EXPRESIONES REGULARES

INDICE

TEMA 4.-EXPRESIONES REGULARES

1.-DEFINICI�

2.-EQUIVALENCIA ENTRE EXPRESIÓN REGULAR Y AFD

Se entiende por Expresi� Regular a la forma compacta de representar los lenguajes. Por lo cual a partir de la expresión regular podemos pasar directamente a su automáta y viceversa.

DEFINICION:

Si A es un alfabeto, una expresión regular sobre este alfabeto se define de la siguiente forma:

f es una expresión regular que denota el lenguaje vacio ( el que no tiene ninguna cadena) automáta sin ningn estado.

e es una expresión regular que denota el lenguaje {e }.

si a∈ A, a es una expresión regular que denota el lenguaje {a}.

Si r y s son expresiones regularesdenotando los lenguajes R y S entonces (r+s) es una expresión regular que denota el lenguaje R∪ S.

Si (rs) es una expresión regular que denota el lenguaje RS.

r* es una expresión regular que denota el lenguaje R*.

A partir de esta definición se puede determinar las expresiones regulares sobre un determinado alfabeto. El tipo de leguaje al que está asociadas las expresiones regulares son los lenguajes regulares.

En las expresiones regulares se pueden eliminar los paréntesis siempre que no haya dudas, la precedencia de las operaciones es: Clausura *, Concatenación , Unión .

EJEMPLOS:

Obtener la expresión regular que representa el lenguaje L={01ⁱ / i =0}

{01ⁱ / i =0}={0}{1ⁱ / i=0}={0}{1}* = 0 1* la expresión regular correspondiente.

Obtener la expresión regular que represente el lenguaje cuyas cadenas está formadas por ceros y unos en cualquier posición, L={u /u∈ {0,1}*}

Sea u=01001 una cadena con una combinación de ceros y unos cualquiera entonces su correspondiente expresión regular será {0}{1}. Como lo que nos piden es ceros y unos en cualquier posición , aplicamos la operación de clausura * obteniendo: ({0}∪ {1})* por tanto la expresión regular que resulta es la siguiente (0+1)*

Dada la expresión regular (a+ε )b* obtener el lenguaje que representa: Sea (a+ε ) el lenguaje 1 notado L_1. Sea b* el lenguaje 2 notado L_2. L₁={a}∪ {ε } y L₂={b}* ={bⁱ /i=0} ,por tanto, L=L₁∪ L₂se especifica de la siguiente forma: L={uv/ u∈ L₁, v∈ L₂}= {abⁱ / i=0}

Obtener el lenguaje asociado a la expresión regular 0*1*

Sea L₁= 0* y L₂=1* sus correspondientes expresiones regulares son L₁={0}*={0ⁱ /i=0} L₂={1}*={1^j /j =0} Por tanto, L= L₁ L₂ ={0ⁱ1^j / i, j=0} es el lenguaje regular asociado a la expresión dada.

Obtener el lenguaje asociado a la expresión regular (1+10)*

Representa el lenguaje que empieza por uno y no contiene dos ceros consecutivos.

EQUIVALENCIA ENTRE EXPRESION REGULAR Y AFD.

Teorema:dada una expresión regular existe un automáta finito que acepta el lenguaje asociado a esta expresión regular. Por tanto existe una equivalencia entre la expresión regular y el automáta finito determinístico.

Para ello tenemos como base los AFD asociados a las expresiones regulares siguientes:

f su automáta es el que no tiene ningún estado, es decir,

e su automáta asociado es

Si a∈ A es una expresión regular su automáta asociado es

El automáta asociado a la expresión (r+s) es

El automáta asociado a la expresión (rs) es

El automáta asociado a la expresión r* es

Conociendo estos automátas podemos pasar a ver algunos ejemplos para construir AFD que acepten un lenguaje correspondiente a la expresión regular dada.

EJEMPLOS:
Construir el AFD que acepte el mismo lenguaje que el asociado a la expresión regular r=01*+1.

Obtenido el AFND CON TN podemos usar algoritmos que transforma:
AFND CON TN a AFND
AFND a AFD
AFD a AFD MINIMAL